home *** CD-ROM | disk | FTP | other *** search
/ Multimedia Selection / Multimedia Selection Volume One - CD-ROM / MULTIMEDIA SELECTION____________.ISO / programz / ldb / binder.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-25  |  12.8 KB  |  683 lines
  1. /*
  2.  
  3.     binder.cpp
  4.     10-25-91
  5.     Loose Data Binder v 1.5
  6.  
  7.     Copyright 1991
  8.     John W. Small
  9.     All rights reserved
  10.  
  11.     PSW / Power SoftWare
  12.     P.O. Box 10072
  13.     McLean, Virginia 22102 8072 USA
  14.  
  15.     John Small
  16.     Voice: (703) 759-3838
  17.     CIS: 73757,2233
  18.  
  19. */
  20.  
  21.  
  22. #include <string.h>
  23. #include "binder.hpp"
  24.  
  25. void Binder::construct(unsigned flags, unsigned maxNodes,
  26.     unsigned limit, unsigned delta)
  27. {
  28.     curNode = first = nodes = 0;
  29.     comparE = BDRcomparE0;
  30.  
  31. /*
  32.     The following relationships are maintained
  33.     during operation of a binder:
  34.  
  35.     1 <= delta <= lowLimit <= limit <= maxNodes
  36.         <= BDR_MAXNODES
  37.     lowThreshold = lowLimit - delta;
  38. */
  39.  
  40.     if (maxNodes > BDR_MAXNODES)
  41.         maxNodes = BDR_MAXNODES;
  42.     if (limit > maxNodes)
  43.         limit = maxNodes;
  44.     if (delta > limit)
  45.         delta = limit;
  46.     if (!delta)  {
  47.         delta = 1;
  48.         if (limit < delta)
  49.             limit = delta;
  50.         if (maxNodes < limit)
  51.             maxNodes = limit;
  52.     }
  53.     if ((linkS = new voiD[limit]) == voiDV0)
  54.         this->limit = lowLimit = lowThreshold
  55.             = this->delta = this->maxNodes
  56.             = this->flags = 0;
  57.     else  {
  58.         this->limit = limit;
  59.         this->delta = delta;
  60.         this->maxNodes = maxNodes;
  61.         lowLimit = limit;
  62.         lowThreshold = lowLimit - delta;
  63.         this->flags = ((flags & BDR_OK_FREE) 
  64.             | BDR_SORTED);
  65.     }
  66. }
  67.  
  68. Binder::Binder(voiDV argv, int argc, unsigned flags)
  69. {
  70.     construct(flags,BDR_MAXNODES,argc,BDR_DELTA);
  71.     if (argv) if (argc > 0)
  72.         while (argc--)
  73.             push(argv[argc]);
  74.     else
  75.         for (argc = 0; insQ(argv[argc]); argc++);
  76. }
  77.  
  78. voiDV Binder::vector()
  79. {
  80.     voiDV V = voiDV0;
  81.  
  82.     if (nodes) if ((V = new voiD[nodes+1]) != voiDV0)  {
  83.         for (unsigned i = 0; i < nodes; i++)
  84.             V[i] = atGet(i);
  85.         V[i] = voiD0;
  86.     }
  87.     return V;
  88. }
  89.  
  90. Binder::~Binder()
  91. {
  92.     if (flags & BDR_OK_FREE)
  93.         allFree();
  94.     else
  95.         allDel();
  96.     if (linkS)
  97.         delete linkS;
  98. }
  99.  
  100. unsigned Binder::setLimit(unsigned newLimit)
  101. {
  102.     voiDV newLinkS;
  103.     unsigned i;
  104.  
  105.     if (newLimit < nodes)
  106.         newLimit = nodes;
  107.     else if (newLimit > maxNodes)
  108.         newLimit = maxNodes;
  109.     if (newLimit < delta)
  110.         newLimit = delta;
  111.     if (!linkS || !newLimit || newLimit == limit)
  112.         return 0;
  113.     if ((newLinkS = new voiD[newLimit]) == voiDV0)
  114.         return 0;
  115.     if ((i = limit - first) > nodes)
  116.         i = nodes;
  117.     memcpy(newLinkS,&linkS[first],sizeof(linkS[0])*i);
  118.     /* copy wrap around */
  119.     if (i < nodes)
  120.         memcpy(&newLinkS[i],linkS,
  121.             sizeof(linkS[0])*(nodes-i));
  122.     if (newLimit > limit)
  123.         if (newLimit - delta > limit)
  124.             lowLimit = newLimit - delta;
  125.         else
  126.             lowLimit = limit;
  127.     else
  128.         if (newLimit - delta > delta)
  129.             lowLimit = newLimit - delta;
  130.         else
  131.             lowLimit = delta;
  132.     lowThreshold = lowLimit - delta;
  133.     delete linkS;
  134.     linkS = newLinkS;
  135.     limit = newLimit;
  136.     first = 0;
  137.     return limit;
  138. }
  139.  
  140. unsigned Binder::setDelta(unsigned newDelta)
  141. {
  142.     return ((newDelta && newDelta <= lowLimit)?
  143.         delta = newDelta : 0);
  144. }
  145.  
  146. unsigned Binder::setMaxNodes(unsigned newMaxNodes)
  147. {
  148.     return ((newMaxNodes >= limit)?
  149.         (maxNodes = (newMaxNodes
  150.         > BDR_MAXNODES)? BDR_MAXNODES
  151.         : newMaxNodes) : 0);
  152. }
  153.  
  154. voiD Binder::atIns(unsigned n, voiD D)
  155. {
  156.     voiDV newLinkS;
  157.     unsigned newLimit, i;
  158.  
  159.     if (!linkS || !D)
  160.         return voiD0;
  161.     if (nodes == limit)  {
  162.         if (limit == maxNodes)
  163.             return voiD0;
  164.         newLimit = (maxNodes - delta > limit)?
  165.             limit + delta : maxNodes;
  166.         if ((newLinkS = new voiD[newLimit])
  167.             == voiDV0) return voiD0;
  168.         if ((i = limit - first) > nodes)
  169.             i = nodes;
  170.         memcpy(newLinkS,&linkS[first],
  171.             sizeof(linkS[0])*i);
  172.         /* copy wrap around */
  173.         if (i < nodes)
  174.             memcpy(&newLinkS[i],linkS,
  175.                 sizeof(linkS[0])*(nodes-i));
  176.         /*
  177.             Compute next smaller linkS size
  178.             and threshold for shrinking.
  179.         */
  180.         lowLimit = limit;
  181.         lowThreshold = lowLimit - delta;
  182.         /* swap new for old */
  183.         delete linkS;
  184.         linkS = newLinkS;
  185.         limit = newLimit;
  186.         first = 0;
  187.     }
  188.     if (!Dattach(D))
  189.         return voiD0;
  190.     if (!n)  /* push */
  191.         linkS[first? --first
  192.             : (first = limit - 1)] = D;
  193.     else if (n >= nodes) /* insQ */
  194.         linkS[(first+(n=nodes))%limit] = D;
  195.     else  { /* insert interior */
  196.         i = (first + n) % limit;
  197.         if (i < first || !first)
  198.             /* move rear rightward */
  199.             memmove(&linkS[i+1],&linkS[i],
  200.                 sizeof(linkS[0])
  201.                 * (nodes-n));
  202.         else /* move front leftward */
  203.             memmove(&linkS[--first],&linkS[--i],
  204.                 sizeof(linkS[0])*(n+1));
  205.         linkS[i] = D;
  206.     }
  207.     nodes++;
  208.     if (n <= curNode)
  209.         curNode++;
  210.     flags &= ~BDR_SORTED;
  211.     return D;
  212. }
  213.  
  214. voiD Binder::atDel(unsigned n)
  215. {
  216.     voiDV newLinkS;
  217.     unsigned newLimit, i;
  218.     voiD D;
  219.  
  220.     if (!linkS || n >= nodes)
  221.         return voiD0;
  222.     D = linkS[(first+n)%limit];
  223.     if (!n)  {  /* pop */
  224.         if (++first >= limit)
  225.             first = 0;
  226.     }
  227.     else if (n != nodes-1)  {  /* del interior */
  228.         /* move front rightward */
  229.         memmove(&linkS[first+1],&linkS[first],
  230.             sizeof(linkS[0])*n);
  231.         first++;
  232.     }
  233.     if (--nodes == 0)
  234.         flags |= BDR_SORTED;
  235.     if (n < curNode)
  236.         curNode--;
  237.     else if (n == curNode)
  238.         curNode = nodes;
  239.     if (nodes < lowThreshold)  {
  240.         newLimit = lowLimit;
  241.         if ((newLinkS = new voiD[newLimit])
  242.             != voiDV0)  {
  243.             if ((i = limit - first) > nodes)
  244.                 i = nodes;
  245.             memcpy(newLinkS,&linkS[first],
  246.                 sizeof(linkS[0])*i);
  247.             /* copy wrap around */
  248.             if (i < nodes)
  249.                 memcpy(&newLinkS[i],linkS,
  250.                     sizeof(linkS[0])
  251.                     *(nodes-i));
  252.             /*
  253.                 Compute next smaller linkS
  254.                 size and threshold for 
  255.                 shrinking.
  256.             */
  257.             if (lowLimit - delta > delta)
  258.                 lowLimit -= delta;
  259.             else
  260.                 lowLimit = delta;
  261.             lowThreshold = lowLimit - delta;
  262.             /* swap new for old */
  263.             delete linkS;
  264.             linkS = newLinkS;
  265.             limit = newLimit;
  266.             first = 0;
  267.         }
  268.     }
  269.     Ddetach(D);
  270.     return D;
  271. }
  272.  
  273. int Binder::allDel()
  274. {
  275.     if (!linkS)
  276.         return 0;
  277.     while (atDel(0))
  278.         /* null stmt */ ;
  279.     return 1;
  280. }
  281.  
  282. int Binder::allFree()
  283. {
  284.     if (!linkS)
  285.         return 0;
  286.     if (flags & BDR_OK_FREE)
  287.         while (Dfree(atDel(0)))
  288.             /* null stmt */ ;
  289.     return 1;
  290. }
  291.  
  292. voiD Binder::atPut(unsigned n, voiD D)
  293. {
  294.     if (linkS && D && (n < nodes))
  295.         if (Dattach(D))  {
  296.             flags &= ~BDR_SORTED;
  297.             voiD& N = linkS[(first+n)%limit];
  298.             Ddetach(N);
  299.             if (flags & BDR_OK_FREE)
  300.                 Dfree(N);
  301.             return (N=D);
  302.         }
  303.     return voiD0;
  304. }
  305.  
  306. voiD Binder::atGet(unsigned n)
  307. {
  308.     return ((linkS && (n < nodes))?
  309.         linkS[(first+n)%limit] : voiD0);
  310. }
  311.  
  312. voiD Binder::atXchg(unsigned n, voiD D)
  313. {
  314.     if (linkS && D && (n < nodes))
  315.         if (Dattach(D))  {
  316.             flags &= ~BDR_SORTED;
  317.             voiD& N = linkS[(first+n)%limit];
  318.             voiD oldD = N;
  319.             N = D;
  320.             Ddetach(oldD);
  321.             return oldD;
  322.         }
  323.     return voiD0;
  324. }
  325.  
  326. unsigned Binder::index(const voiD D)
  327. {
  328.     unsigned i;
  329.  
  330.     if (linkS && D)
  331.         for (i = 0; i < nodes; i++)
  332.             if (D == linkS[(first+i)%limit])
  333.                 return i;
  334.     return BDR_NOTFOUND;
  335. }
  336.  
  337. int Binder::forEach(BDRforEachBlocK B, voiD M, voiD A)
  338. {
  339.     unsigned i;
  340.  
  341.     if (!linkS || !B || !nodes)
  342.         return 0;
  343.     for (i = 0; i < nodes; i++)
  344.         (*B)(linkS[(first+i)%limit],M,A);
  345.     return 1;
  346. }
  347.  
  348. unsigned Binder::firstThat(BDRdetectBlocK B, voiD M)
  349. {
  350.     unsigned i;
  351.  
  352.     if (linkS && B)
  353.         for (i = 0; i < nodes; i++)
  354.             if ((*B)(linkS[(first+i)%limit],M))
  355.                 return i;
  356.     return BDR_NOTFOUND;
  357. }
  358.  
  359. unsigned Binder::lastThat(BDRdetectBlocK B, voiD M)
  360. {
  361.     unsigned i;
  362.  
  363.     if (linkS && B && nodes)
  364.         for (i = nodes; i--; /* no reinit */)
  365.             if ((*B)(linkS[(first+i)%limit],M))
  366.                 return i;
  367.     return BDR_NOTFOUND;
  368. }
  369.  
  370. int Binder::collect(BDRcollectBlocK B, BindeR R,
  371.     voiD M, voiD A)
  372. {
  373.     unsigned i;
  374.  
  375.     if (!linkS || !B || !R)
  376.         return 0;
  377.     for (i = 0; i < nodes; i++)
  378.         (*B)(linkS[(first+i)%limit],R,M,A);
  379.     return 1;
  380. }
  381.  
  382.  
  383. /*  FlexList like primitives:  */
  384.  
  385. unsigned Binder::CurNode()
  386. {
  387.     return ((curNode < nodes)?
  388.         curNode : BDR_NOTFOUND);
  389. }
  390.  
  391. int  Binder::setCurNode(unsigned n)
  392. {
  393.     return ((curNode = ((n > nodes)? nodes : n))
  394.         < nodes);
  395. }
  396.  
  397. Binder& Binder::operator<<(Binder& (*manipulator)
  398.         (Binder& B))
  399. {
  400.     return (manipulator? (*manipulator)(*this)
  401.         : *this);
  402. }
  403.  
  404. voiD Binder::ins(voiD D)
  405. {
  406.     if (atIns(curNode+1,D))  {
  407.         if (++curNode >= nodes)
  408.             curNode = nodes - 1;
  409.         return D;
  410.     }
  411.     return voiD0;
  412. }
  413.  
  414. voiD Binder::insSort(voiD D)
  415. {
  416.     unsigned low, mid, high;
  417.     voiD ok;
  418.  
  419. /*
  420.     The current node is left undefined if
  421.     anything fails, otherwise it is set to the
  422.     newly inserted node.
  423. */
  424.  
  425.     curNode = nodes;
  426.     if (!linkS || !D || nodes >= maxNodes || !comparE)
  427.         return voiD0;
  428.     if (!(flags & BDR_SORTED))
  429.         if (!sort())
  430.             return voiD0;
  431.     low = 0;
  432.     high = nodes;
  433.     while (low < high)  {
  434.         mid = low + ((high - low) >> 1);
  435.         if ((*comparE)(D,
  436.             linkS[(first+mid)%limit]) <= 0)
  437.             high = mid;
  438.         else
  439.             low = mid + 1;
  440.     }
  441.     if ((ok = atIns(high,D)) != voiD0)
  442.         curNode = high;
  443.     /*  atIns() resets sorted to zero  */
  444.     flags |= BDR_SORTED;
  445.     return ok;
  446. }
  447.  
  448. voiD Binder::del()
  449. {
  450.     voiD D;
  451.     unsigned n;
  452.  
  453.     if ((D = atDel(n=curNode)) != voiD0)
  454.         if (n--)
  455.             curNode = n;
  456.     return D;
  457. }
  458.  
  459. voiD Binder::next()
  460. { 
  461.     if (linkS)  {
  462.         if (curNode >= nodes)
  463.             curNode = 0;
  464.         else
  465.             curNode++;
  466.         if (curNode < nodes)
  467.             return linkS[(first+curNode)%limit];
  468.     }
  469.     return voiD0;
  470. }
  471.  
  472. voiD Binder::prev()
  473. { 
  474.     if (linkS)  {
  475.         if (curNode)  {
  476.             if (curNode > nodes)
  477.                 curNode = nodes;
  478.             curNode--;
  479.         }
  480.         else
  481.             curNode = nodes;
  482.         if (curNode < nodes)
  483.             return linkS[(first+curNode)%limit];
  484.     }
  485.     return voiD0;
  486. }
  487.  
  488. voiD Binder::findFirst(const voiD K)
  489. {
  490.     unsigned low, mid, high;
  491.     voiD D;
  492.  
  493. /*
  494.     The current node is left undefined if
  495.     anything fails, otherwise it is set to the
  496.     newly found node.
  497. */
  498.  
  499.     curNode = nodes;
  500.     if (!linkS || !K || !comparE || !nodes)
  501.         return voiD0;
  502.     if (flags & BDR_SORTED)  {
  503.         low = 0;
  504.         high = nodes;
  505.         while (low < high)  {
  506.             mid = low + ((high - low) >> 1);
  507.             if ((*comparE)(K,linkS[(first+mid)
  508.                 %limit]) <= 0)
  509.                 high = mid;
  510.             else
  511.                 low = mid + 1;
  512.         }
  513.         if (high < nodes)
  514.             if (!(*comparE)(K,linkS[(first+
  515.                 high)%limit]))
  516.                 return linkS[(first+
  517.                 (curNode = high))%limit];
  518.     }
  519.     else  {  /*  linear search!  */
  520.         while ((D = next()) != voiD0)
  521.             if (!(*comparE)(K,D))
  522.                 return D;
  523.     }
  524.     return voiD0;
  525. }
  526.  
  527. voiD Binder::findNext(const voiD K)
  528. {
  529.  
  530. /*
  531.     For sorted binders you must first call findFirst()
  532.     to insure consistent results!
  533. */
  534.  
  535.     voiD D;
  536.  
  537. /*
  538.     The current node is left undefined if
  539.     anything fails, otherwise it is set to the
  540.     newly found node.
  541. */
  542.  
  543.     if (!linkS || !K || !comparE)  {
  544.         curNode = nodes;
  545.         return voiD0;
  546.     }
  547.     while ((D = next()) != voiD0)
  548.         if (!(*comparE)(K,D))
  549.             return D;
  550.         else if (flags & BDR_SORTED)  {
  551.             curNode = nodes;
  552.             break; /*  Look no further!  */
  553.         }
  554.     return voiD0;
  555. }
  556.  
  557. voiD Binder::findLast(const voiD K)
  558. {
  559.     unsigned low, mid, high;
  560.     voiD D;
  561.  
  562. /*
  563.     The current node is left undefined if
  564.     anything fails, otherwise it is set to the
  565.     newly found node.
  566. */
  567.  
  568.     curNode = nodes;
  569.     if (!linkS || !K || !comparE || !nodes)
  570.         return voiD0;
  571.     if (flags & BDR_SORTED)  {
  572.         low = 0;
  573.         high = nodes;
  574.         while (low < high)  {
  575.             mid = low + ((high - low) >> 1);
  576.             if ((*comparE)(K,linkS[(first+mid)
  577.                 %limit]) < 0)
  578.                 high = mid;
  579.             else
  580.                 low = mid + 1;
  581.         }
  582.         if (high < nodes)
  583.             if (!(*comparE)(K,linkS[(first+
  584.                 high)%limit]))
  585.                 return linkS[(first+
  586.                 (curNode = high))%limit];
  587.     }
  588.     else  {  /*  linear search!  */
  589.         while ((D = prev()) != voiD0)
  590.             if (!(*comparE)(K,D))
  591.                 return D;
  592.     }
  593.     return voiD0;
  594. }
  595.  
  596. voiD Binder::findPrev(const voiD K)
  597. {
  598.  
  599. /*
  600.     For sorted binders you must first call findLast()
  601.     to insure consistent results!
  602. */
  603.  
  604.     voiD D;
  605.  
  606. /*
  607.     The current node is left undefined if
  608.     anything fails, otherwise it is set to the
  609.     newly found node.
  610. */
  611.  
  612.     if (!linkS || !K || !comparE)  {
  613.         curNode = nodes;
  614.         return voiD0;
  615.     }
  616.     while ((D = prev()) != voiD0)
  617.         if (!(*comparE)(K,D))
  618.             return D;
  619.         else if (flags & BDR_SORTED)  {
  620.             curNode = nodes;
  621.             break; /*  Look no further!  */
  622.         }
  623.     return voiD0;
  624. }
  625.  
  626. int   Binder::sort(BDRcomparE comparE)
  627. {
  628.     unsigned low, mid, high;
  629.     unsigned d;
  630.     voiD D;
  631.  
  632. /*
  633.     The current node is always reset to undefined
  634.     regardless of the outcome of sort.
  635. */
  636.  
  637.     curNode = nodes;
  638.     if (flags & BDR_SORTED)  {
  639.         if (this->comparE == comparE || !comparE)
  640.             return 1;
  641.     }
  642.     else if (!this->comparE && !comparE)
  643.         return 0;
  644.     if (comparE)  {
  645.         this->comparE = comparE;
  646.         flags &= ~BDR_SORTED;
  647.     }
  648.     if (!nodes)
  649.         return (flags |= BDR_SORTED);
  650.     if (!linkS)
  651.         return 0;
  652.     if (first)  { /* form contiguous block at front */
  653.         d = (first + nodes) % limit;
  654.         if (d > first)
  655.             memmove(linkS,&linkS[first],
  656.                 sizeof(linkS[0])*nodes);
  657.         else if (d < first)
  658.             memmove(&linkS[d],&linkS[first],
  659.                 sizeof(linkS[0])
  660.                 *(limit-first));
  661.         /* else array is full/contiguous */
  662.         first = 0;
  663.     }
  664.     for (high = d = 1; d < nodes; high = ++d)  {
  665.         low = 0;
  666.         D = linkS[d];
  667.         while (low < high)  {
  668.             mid = low + ((high - low) >> 1);
  669.             if ((*this->comparE)(D,
  670.                 linkS[mid]) <= 0)
  671.                 high = mid;
  672.             else
  673.                 low = mid + 1;
  674.         }
  675.         if (high < d)  {
  676.             memmove(&linkS[high+1],&linkS[high],
  677.                 sizeof(linkS[0])*(d-high));
  678.             linkS[high] = D;
  679.         }
  680.     }
  681.     return (flags |= BDR_SORTED);
  682. }
  683.